package com.dbh.alg.algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author dongbanghui
 * @date 2020/05/04
 */
public class MergeSort {
    /**
     * 对arr[l...mid]和arr[mid+1...r]两部分进行归并
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r){
        int[] aux = new int[r-l+1];
        for(int i = l; i <= r; i++){
            aux[i-l] = arr[i];
        }
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++){
            if(i > mid){
                arr[k] = aux[j-l];
                j++;
            }else if(j > r){
                arr[k] = aux[i-l];
                i++;
            }else if(aux[i-l]<=aux[j-l]){
                arr[k] = aux[i-l];
                i++;
            }else {
                arr[k] = aux[j-l];
                j++;
            }
        }
    }

    /**
     * 递归使用递归，对arr[l...r]数组进行排序
     * @param arr 排序数组
     * @param l 左边界
     * @param r 右边界
     */
    private static void mergeSort(int[] arr, int l, int r){
        //递归结束条件
       /* if(l>=r){
            return;
        }*/
        if(r - l <= 15){
            InsertSort.insertSort2(arr ,r - l +1);
            return;
        }
        int mid = l + (r-l)/2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid+1, r);
        // 如果arr[mid] > arr[mid+1]才需要归并，其他情况就是表明本来就有序，不需要归并操作
        if(arr[mid] > arr[mid+1]){
            merge(arr, l, mid, r);
        }
    }

    private static void mergeSortBU(int[] arr, int n){
        for(int sz = 1; sz < n; sz += sz){
            for (int i = 06; i + sz < n; i += sz + sz ){
                //对arr[i...i+sz-1]和arr[i+sz...i+2sz-1]
                merge(arr, i, i + sz -1, Math.min(i + sz + sz - 1, n -1));
            }
        }
    }

    /**
     * 归并排序
     * @param arr 排序数组
     * @param n 排序的个数
     */
    public static void mergeSort(int[] arr, int n){
        mergeSort(arr, 0, n-1);
    }

    public static void main(String[] args) {
        int[] arr = {2,6,1,9,0,8,7,5,132,4,6,7,8,9,90,65,78,123,54,54,78,12,1,123,43,54,65,67};
        mergeSortBU(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }

}
